package 算法回顾;

import 多线程.S;

import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 总结：推排序实际上就是将数组转换成平衡二叉树
 * 首先将数组转换成一个大顶堆
 * 再将堆顶（最大值与最后一个值（最小值）交换，将最大值提取（len--，并执行heapify(a,0,len);）
 * 剩下的堆再进行大顶堆化
 * 时间辅助度：O(nlogn)
 */
public class Heap_Sort {
    public static void main(String[] args) {
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64};
        for (int x :
                a) {
            System.out.print(x+".");
        }
        sort(a);
        System.out.println("\n--------------排序后-------------");
        for (int x :
                a) {
            System.out.print(x+".");
        }

    }


    public static void sort(int[] a){
        int len=a.length;
        buildMaxHeap(a,len); //形成大顶堆
        for (int i= a.length-1;i>=0;i--){
            swap(a,0,i);
            len--;
            heapify(a,0,len);
        }
    }

    public static void buildMaxHeap(int[] a ,int size){
        for (int i=a.length/2;i>=0;i--){
            heapify(a,i,size);
        }
    }

    public static void heapify(int[] a,int index,int size){
        int left=2*index;
        int right=2*index+1;
        int largest=index;

        if (left<size && a[largest]<a[left]){
            largest=left;
        }
        if (right<size && a[largest]<a[right]){
            largest=right;
        }
        if (largest!=index){
            //说明index已经被替换
            swap(a,index,largest);
            heapify(a,largest,size);
        }
    }

    private static void swap(int[] a, int i, int j) {
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;


    }
}
